package study.sort1;

import java.util.Arrays;

/**
 * 堆排序
 */
public class HeapSort {

    public static void main(String[] args) {
//        int[] arr = new int[] {7,1,3,10,5,2,8,9,6};
        int[] arr = new int[]{4,7,6,5,3,2,8,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    static void sort(int[] arr) {
        if(arr == null || arr.length <= 1)
            return;
        buildHeap(arr);
        int count = 1;
        for (int i = arr.length - 1; i > 0; i --) {
            int t = arr[0];
            arr[0] = arr[i];
            arr[i] = t;
            sink(arr, 0, i - 1);
            System.out.printf("第%d轮后：%s\n", count ++, Arrays.toString(arr));
        }
    }

    /**
     * 构建堆
     * @param arr
     */
    private static void buildHeap(int[] arr) {
        int cur = (arr.length - 2) / 2; // 最后一个非叶子节点
        int limit = arr.length - 1;
        while(cur >= 0)
            sink(arr, cur --, limit);
    }

    /**
     * 下沉
     * @param arr
     * @param index
     */
    private static void sink(int[] arr, int index, int limit) {
        int t = arr[index];
        int cur = index;
        for(;;) {
            int l = cur * 2 + 1, r = l + 1;
            if (l > limit) // 左节点超过数组长度，说明为空
                break;
            int minIndex = r > limit ? l : arr[l] < arr[r] ? l : r; // 找到最小的子节点
            if(t > arr[minIndex]) {
                arr[cur] = arr[minIndex];
                cur = minIndex;
            } else {
                break;
            }
        }
        if(cur != index)
            arr[cur] = t;
    }
}
